package day_2022_7_to_8.day48;
import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

/**
 * 数组中的第K个最大元素
 * @author haomin
 * @date 2022/07/18 09:50
 **/

// 方法一：调库函数
public class Day4_1_Num215_FindKthLargest {
    class Solution {
        public int findKthLargest(int[] nums, int k) {
            Arrays.sort(nums);
            return nums[nums.length-k];
        }
    }
}

// 方法二：堆排序


// 方法三：快排
class Solution {
    private static final ThreadLocalRandom random = ThreadLocalRandom.current();

    public  int findKthLargest(int[] nums, int k) {
        quickSortInternal(nums,0,nums.length - 1);
        return nums[nums.length - k];
    }

    private  void quickSortInternal(int[] nums, int l, int r) {

        if(r - l <= 0){
            return;
        }
        int p = partition(nums,l,r);

        quickSortInternal(nums,l,p - 1);
        quickSortInternal(nums,p + 1,r);
    }

    private  int partition(int[] nums, int l, int r) {
        int randomIndex = random.nextInt(l,r) ;
        swap(nums,l,randomIndex);
        int v = nums[l];

        int j = l;
        for (int i = l + 1; i <= r ; i++) {
            if(nums[i] < v){
                swap(nums,i,j + 1);
                j++;
            }
        }
        swap(nums,l,j);
        return j;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] =temp;
    }
}